package com.cwj.lab4.SORT;

/**
 * 归并排序
 * 小到大
 * */
public class mergeSort<T extends Comparable<T>>implements Sorted<T> {
    public void Sort(T[] nums) {
        Sort(nums, 0, nums.length - 1, new Comparable[nums.length]);
    }

    public void Sort(T[] nums, int lef, int rig, Comparable<T>[] helNums) {
        if (lef >= rig) {
            return;
        }
        int mid = lef + ((rig - lef) >> 1);
        Sort(nums, lef, mid, helNums);
        Sort(nums, mid + 1, rig, helNums);
        merge(nums, lef, mid, rig, helNums);
    }

    private void merge(T[] nums, int lef, int mid, int rig, Comparable<T>[] helNums) {

//         while(lef <=mid&&beg<=rig){
//             int t_res=nums[lef].compareTo(nums[beg]);
//             if(t_res<=0){
//                 helNums[top++]=nums[lef++];
//             }else {
//                 helNums[top++]=nums[beg++];
//             }
//         }
//         while(lef<=mid){
//             helNums[top++]=nums[lef++];
//         }
//         while(beg<=rig){
//             helNums[top++]=nums[beg++];
//         }
        int start = lef;
        int beg = mid + 1;
//        int top = lef;
        for (int i = lef; i <= rig; i++) {
            if (start > mid)
                helNums[i] = nums[beg++];
            else if (beg > rig)
                helNums[i] = nums[start++];
            else if (nums[start].compareTo(nums[beg]) <= 0)
                helNums[i] = nums[start++];
            else
                helNums[i] = nums[beg++];
        }
        for (int i = lef; i <= rig; i++) {
            nums[i] = (T) helNums[i];
        }
        //复制数组
        //Arrays.Copy();
    }

}
